ECOC(Error-correcting output codes)

multi classifer 문제를 위해, binary classifier를 기반으로 처리하는 Ensemble기법의 일종.

각 class에 대해 이진 코드(word)를 할당하고, binary classifier들의 출력을 기반으로 최종 class를 예측한다.

Code Matrix

W

M \times L

matrix로, class와 binary classifier를 정의하는 matrix이다.

4개의 classifier, 4개의 class.

+ 1 > - 1 > - 1 > - 1 - 1 + 1 - 1 - 1 - 1 - 1 + 1 - 1 - 1 - 1 - 1 + 1

: 전부 negative, positive인 것은 의미가 없으니 이를 제외한다.

각 class에 할당된 binary code 간의 Hamming Distance가 크도록 만든다. 또한, Column(각 classifier)에 대해서도 Hamming Distance가 크도록 만든다.

서로 간의 Hamming Distance가 클수록 오류가 발생해도 차이가 크게 나게 되므로, 가장 가까운 binary code로 복구 되도록 하여 Error 정정 능력이 올라가기 때문이다.

또한, column에 대해서는 class간의 구별 가능성이 높아지므로 성능이 좋아진다.

Test Data에 대한 prediction과, Code matrix의 각 행과의 Hamming Distance들 중 가장 작은 것으로 예측한다.

하지만, hamming distance가 모두 동일하게 나타날 경우 결정할 수 없다. 이러한 경우에는 Learner를 늘려, Code Matrix의 Column을 추가해 재학습시킨다.

해석해보자면, 각 learner들의 어떠한 class에 대한 이진 예측에 대하여 가장 근접하게(distance가 작은) 접근된 binary code의 class로 예측하는 것이다.

잘못된 binary classifer가 되더라도, 가장 근접한 class를 선택할 확률이 높다.

혹은, $max_{k} l \sum w_{k l} h_{l}$ 의 voting 방식을 이용하기도 한다.